本场链接:Educational Codeforces Round 73
闲话
这场VP出了A~D.但是猜的成分挺高的.
A. 2048 Game
题目大意:给定一个个数的集合,保证其内所有的元素都是的幂.每次你可以从中选出两个数,并把他们俩的和作为新元素放进原集合.而原来的两个数被删掉.问是否能出现2048.只用输出是否.
数据范围:
思路
乱搞即可.规定一个目标,初始为2048,每次看目标的值的数量够不够,如果不够的话就把目标拆解一半,再算新的目标是否足够.注意如果原序列里有原来的目标值,则所需的数量会减少.
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,ll> pil;
#define x first
#define y second
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int n;scanf("%d",&n);
map<ll,int> cnt;
for(int i = 1;i <= n;++i)
{
ll x;scanf("%lld",&x);
++cnt[x];
}
int target = 2048,ok = 0,need = 1;
while(target >= 1)
{
if(cnt[target] >= need)
{
// cout << target << " " << cnt[target] << endl;
ok = 1;
break;
}
need -= cnt[target];
target /= 2;
need *= 2;
}
if(!ok) puts("NO");
else puts("YES");
}
return 0;
}
B. Knights
题目大意:一个的棋盘上放置若干个棋子,每个棋子是两种颜色中的一个.棋子按"日"字型攻击.构造一种摆放方案,使得整个棋局上颜色不同且可以互相攻击到的棋子对的数量最多.
思路
对于每一个点来说,如果他的八个方向的点都是跟他颜色不同的,则自然就是最多的.因此联想到二分图的染色,对这个图一样的处理,即使得颜色不同且互相攻击到的对数最多.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 105;
char g[N][N];
int main()
{
int n;scanf("%d",&n);
for(int i = 1;i <= n;++i)
for(int j = 1;j <= n;++j)
if((i + j) & 1) g[i][j] = 'W';
else g[i][j] = 'B';
for(int i = 1;i <= n;++i)
{
for(int j = 1;j <= n;++j)
printf("%c",g[i][j]);
puts("");
}
return 0;
}
C. Perfect Team
题目大意:三种类型的零件各有个,一个机器里要有恰好三个零件,其中零件的数量不得少于.问最多能组合出多少种.
思路
显然应该先满足的情况,在组合的前提下算出一个结果,之后问题就又等价成了只有的时候有多少种组合方式.由于此时的类型没有什么区别,因此可以交换使得.这个时候还有两种构造机器的方式:一种是另一种是.假设在最后的答案里,前者有个后者有个,那么显然答案就是,根据不等式关系有.但是答案不是直接加上这个数就结束了的,因为还有一个极端情况:如果此时的话,原来的不等式的右侧就有:即此时如果选择答案可能会变得更好,这是一个特殊情况,需要额外考虑.
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
int main()
{
int T;scanf("%d",&T);
while(T--)
{
int a,b,c;scanf("%d%d%d",&a,&b,&c);
int res = 0;
res += min({a,b,c});
a -= res;b -= res;c -= res;
if(a > b) swap(a,b);
if(a * 2 <= b)
{
res += a;
b -= a;
a = 0;
}
else res += (a + b) / 3;
printf("%d\n",res);
}
return 0;
}
D. Make The Fence Great Again
题目大意:有个元素,每个元素有两个属性和,表示如果要让增加所要付出的代价.现在要使整个序列里不存在相邻的两个元素的值相同.问最小化费是多少.
思路
这个题一拿到手会发现非常像.但是由于数的范围会导致整个空间开不够,而且也不能靠滚动数组优化空间.因此思路就断了,如果继续想贪心构造会发现这个题也没什么突破口.dp关键的一个问题就是值域太大了,那么有没有办法使第二维的值域变小呢?答案是肯定的.
对于每个元素来说,他的值增加的次数是不超过的,关于这一点可以手推验证.只要运用这个性质,就可以把第二维的空间压下来了.
状态:表示当前在元素上,这个元素要增加次.
入口:
转移:当且仅当时,
出口:
注意,本题的答案范围是,这意味着要开.不过这还不是重点,重点是即数组的初值一定要根据类型设置大小,因为这里是所以设置的是如果开成就会WA.
代码:
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define int ll
const int N = 3e5+7,INF = (1ll << 60);
int a[N],b[N],f[N][3];
signed main()
{
int T;scanf("%lld",&T);
while(T--)
{
int n;scanf("%lld",&n);
for(int i = 1;i <= n;++i) scanf("%lld%lld",&a[i],&b[i]);
f[1][0] = 0;f[1][1] = b[1];f[1][2] = 2 * b[1];
for(int i = 2;i <= n;++i)
for(int j = 0;j <= 2;++j)
{
f[i][j] = INF;
for(int k = 0;k <= 2;++k)
if(a[i - 1] + k != a[i] + j)
f[i][j] = min(f[i][j],f[i - 1][k] + j * b[i]);
}
printf("%lld\n",min({f[n][0],f[n][1],f[n][2]}));
}
return 0;
}